#pragma once

#include <vector>
#include <memory>

struct Edge // vertices numbers are 0-based;
{
	int begin, end;
	Edge() : begin(0), end(0) {}
	Edge (int begin, int end) : begin(begin), end(end) {}
};

class IDigraph
{
public:
	virtual int getNumberOfVertices() const = 0;
	virtual std::vector<int> getIncidenceList(int vertex) const = 0;
	virtual bool isEdge(const Edge &edge) const = 0;
	virtual size_t byteSize() const = 0;
	virtual ~IDigraph();
};

class IMatrixGraph : public IDigraph
{
public:
	explicit IMatrixGraph(const std::vector<Edge> &edges, int vertices_num);
	int getNumberOfVertices() const;
	std::vector<int> getIncidenceList(int vertex) const;
	bool isEdge(const Edge &edge) const;
	size_t byteSize() const;
private:
	int vertices_num_;
	std::vector< std::vector<bool> > matrix_;
};

class IListGraph : public IDigraph
{
public:
	explicit IListGraph(const std::vector<Edge> &edges, int vertices_num);
	int getNumberOfVertices() const;
	bool isEdge(const Edge &edge) const;
	std::vector<int> getIncidenceList(int vertex) const;

	size_t byteSize() const;
private:
	int vertices_num_;
	std::vector<int> list_;
	std::vector<int> offsets_;
};